\chapter{LL1}

\section{LL(1)文法定义}

\SparkleBold

上一节中我们提到过，语法分析方法通常分成两大类，分别是自顶向下法（推导法）和自底向上法（归约法）。递归子程序是其中的一种自上而下的方法。

下面要介绍的是第二种自上而下的方法，也是一种基于推导的方法，叫LL(1)分析法。为什么叫LL(1)分析法？这两个‘L’都是有意义的：第一个‘L’指的是自左向右扫描，即算法（程序）对字符串进行分析的时候是自左向右扫描的；第二个‘L’指的是最左推导，即算法要求推导最左边可推导的非终结符。括号里的“1”指的是只查看当前的一个符号。为了简单的理解上述内容，我们给出一个例子。\\

	\begin{tcolorbox}[colback=blue!5!white,colframe=blue!75!black,title=文法定义]
	\centering
	S $\rightarrow$ 主谓宾 \\
	主 $\rightarrow$ 我$|$你$|$它$|$小牛\\
	谓 $\rightarrow$ 研究$|$学习\\
	宾 $\rightarrow$ 主$|$自然语言技术\\
\end{tcolorbox}
现在需要检查\textbf{目标语句}“小牛研究自然语言技术”是否归属于这个文法，我们从开始符号S出发得到\textbf{分析短语}主谓宾。对目标短语从左往右逐个扫描的分析策略是第一个L，对分析短语自左向右推导就是第二个L(具体的说，就是当分析短语存在多个非终结符的时候，我们总是从最左侧的非终结符开始推导)。
\begin{enumerate}
	\item S $\rightarrow$ 主谓宾
	\item 从目标语句中读入“小”字，确定 主 $\rightarrow$ 小牛
	\item 从目标语句中读入“牛”字，匹配
	\item 从目标语句中读入“研”字，确定 谓 $\rightarrow$ 研究
	\item 从目标语句中读入“究”字，匹配
	\item 从目标语句中读入“自”字，确定 宾 $\rightarrow$ 自然语言技术\\
	....接下来就全是匹配过程
\end{enumerate}
在上面的分析流程中，我们确定推导式子，只需要读入一个字符即可，这就是LL(1)的1的含义。既然有LL(1)，那么也可以看更多字符再决定选用什么式子推导，也就是LL(2)、LL(3)等等。观察更多的字符对相同左部的产生式右部有相同的前缀会有更多的容忍，比如刚刚的主语如果还能推导出小刚，那我们需要再多看一个字符才能决定主语要推出什么右部。

LL(1)分析法还有一种别的称呼，叫预测分析法。“预测”指的是根据当前的状态，能够知道接下来使用的是哪条产生式。刚才已经提到，LL(1)分析法与递归子程序一样，都是自上而下的，而且是确定性文法的分析方法。对于LL(1)分析法，有三个基本的要点：\\
\begin{tcolorbox}[colback=blue!5!white,colframe=blue!75!black,title=※\ 三个基本要点]
	\begin{enumerate}
		\item 利用一个分析表，登记如何选择产生式的知识；
		\item 利用一个分析栈，记录分析过程；
		\item 此分析法要求文法必须是 LL(1)文法。
	\end{enumerate}
\end{tcolorbox}
更详细的补充说明上述三点：
\begin{enumerate}
	\item LL(1)分析法必须要有一个分析表，这和递归子程序不一样。分析表是什么？分析表登记了一些如何选择产生式的知识，即在某一个时刻状态下，应该用哪个产生式。
	\item LL(1)分析法里面有一个分析栈，是在执行分析方法的时候用的，目的是去记录分析的过程，就是要把分析的状态，通过一个栈的形式记录下来。
	\item LL(1)分析法的前置条件是，所分析的文法必须是LL(1)文法。回顾一下LL(1)文法的两个条件：第一，相同的左部，右部不同的产生式首字母不能相同；第二，不能有左递归。
	....接下来就全是匹配过程
\end{enumerate}
\section{LL(1)分析的完整流程}
\subsection{一个具体例子的演示}
先对LL(1)文法进行感性的认识。首先，把这个产生式进行编号。
\begin{tcolorbox}[colback=red!5!white,colframe=yellow!75!black,title=G(Z):]
	
	Z $\rightarrow$ dAZ ①\quad $|$\quad bA   ②   \\
	\quad	A$\rightarrow$aA  ③\quad $|$\quad $\displaystyle\varepsilon$   ④
	
	
\end{tcolorbox}
四个产生式都进行了编号，其中①、②两个产生式的左部都是Z，③、④两个产生式的左部都是A。对于这些产生式，会得到一个分析表。这个分析表，每一行都对应了一个非终结符，每一列都对应了一个终结符，还有结束的标志‘\#’。
\begin{table*}[h]
	\centering
	\setlength{\tabcolsep}{7mm}{
		\begin{tabular}{|l|l|l|l|l|l|}
			\hline
			& a & b & c & d & \# \\ \hline
			Z  &   & ② &   & ① &    \\ \hline
			A  & ③ & ④ & ④ & ④ &    \\ \hline
	\end{tabular}}
\end{table*}

这样的一个表称为是分析表，通过一个终结符和一个非终结符，就能查到一个表项。表项表示什么？比如，②表示的意思是，非终结符Z，看到了终结符‘b’，就要使用产生式②进行推导。其它项以此类推。

有了分析表之后，就可以用LL(1)分析法进行分析。例如对符号串α=“abc\#”进行分析。分析时需要有一个栈结构，要知道当前的符号是什么，剩余的符号是什么，操作是什么。

\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/1}
	\caption{对符号串α=“abc\#”的分析过程表}
	\label{fig:1}
\end{figure}
首先，要把‘\#’压栈，这是约定。之后还要把起始符号Z压到栈里，因为推导得从起始符号推导。此时，待处理的第一个符号是‘b’，后面的‘a’、‘c’、‘\#’是还没处理的。这个时候该如何执行分析方法？栈顶符号是一个非终结符，就用非终结符Z和当前符号‘b’到分析表里进行查找，对应的是产生式②这一项，因此就要用产生式②进行推导。\\
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/2}
	\caption{根据栈顶元素和当前符号选择操作2}
	\label{fig:2}
\end{figure}

下一个操作，让Z出栈，然后把Z的右部“bAc”逆序压栈，即‘c’、‘A’、‘b’依次进栈。因为栈是先进后出的结构，这样‘b’就能在栈顶，可以先匹配，‘A’次之，‘c’最后。现在栈顶符号和当前符号都是‘b’，也是终结符，因此操作就是匹配‘b’。如Figure \ref{fig:3}所示。
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/3}
	\caption{根据当前符号和栈顶元素进行匹配}
	\label{fig:3}
\end{figure}


匹配‘b’之后，就将‘b’出栈，栈顶符号变成‘A’，当前符号是‘a’，剩余序列是‘c\#’。‘A’是一个非终结符，当前符号是‘a’，到分析表里查，对应项是③，所以应该用产生式③进行推导。如Figure \ref{fig:4}所示。
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/4}
	\caption{根据栈顶元素和当前符号选择产生式}
	\label{fig:4}
\end{figure}

‘A’推导完后，就把‘A’弹出栈，再把产生式③的右部逆序压栈。这时候栈顶是‘a’，当前符号也是‘a’，于是匹配‘a’。如Figure \ref{fig:5}所示。
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/5}
	\caption{根据当前符号和栈顶元素进行匹配}
	\label{fig:5}
\end{figure}


匹配完‘a’后，弹出栈顶符号的同时，当前符号读取下一个，即‘c’，剩余序列只剩一个‘\#’。对于栈顶符号‘A’和当前符号‘c’，查表得④。如Figure \ref{fig:6}所示。
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/6}
	\caption{根据当前符号和栈顶元素选择产生式}
	\label{fig:6}
\end{figure}

这时候选择是空，操作是一样的，把栈顶的非终结符弹出去，右部逆序压栈，空的逆序压栈即没有元素压栈。当前符号是‘c’，所以匹配‘c’。


匹配了‘c’之后把栈顶符号弹出去，这时候就剩下‘\#’，当前符号也处理完了，也剩下‘\#’，说明匹配结果是正确的。
\begin{figure}[h]
	\centering
	\includegraphics[width=0.7\linewidth]{pic/7}
	\caption{最终的匹配流程图}
	\label{fig:7}
\end{figure}

总结一下以上LL(1)分析过程:
\begin{enumerate}
	\item 首先，给文法规则的产生式进行编号，得到一个分析表，分析表的每一行代表一个非终结符，每一列代表一个终结符或表示结束的‘\#’。
	\item 接下来是对符号串α=“bac\#”的分析，先把‘\#’压进栈，然后压一个起始非终结符，之后就根据栈顶符号和当前符号去查分析表找到要做的操作，弹出栈顶符号并将右部逆序压栈。
	\item 如果栈顶符号和当前符号是相同的终结符，就匹配，然后把匹配的元素弹出栈，更新要识别的当前符号。以此类推，直到栈顶符号和当前符号都是‘\#’，即分析正确。
\end{enumerate}

这里有两个问题，分别是:\\
\begin{tcolorbox}[colback=red!15!yellow,colframe=orange!75!black]
	\begin{enumerate}
		\item 选择推导产生式后，为什麽要逆序压栈?
		\item 当栈顶为A,当前单词为c时，为什么选择 A $\rightarrow \varepsilon$?
		
	\end{enumerate}
\end{tcolorbox}



这个地方我不太确定，试着给出这两个问题的答案:\\
\begin{tcolorbox}[colback=red!15!white,colframe=orange!75!black]
	\begin{enumerate}
		\item 我们选择一个产生式是通过分析表，而分析表的形成主要是通过相同左部，分析它右部各子产生式最左端不相同的前缀字符形成的。LL1文法从左侧开始扫描目标语句，每次读入一个字符，正好可以和选中的右部子产生式的第一个左侧字符匹配，所以可以发现每次选取非$\varepsilon$的产生式时下一步一定是一个匹配流程。又因为栈是FILO结构，所以逆序压栈才能保证产生式的左端在栈顶。
		\item 栈顶是非终结符号且当前元素不是其产生式的最左字符，说明这个非终结符处理不了这个情况，只能交给栈中在其下的终结符进行匹配或者非终结符进行生成再匹配。这个问题就好像你想要一杯牛奶结果店里只有咖啡，店员不可能收了你的钱给你一杯咖啡，只会让你去找另一个有牛奶的店买牛奶一个道理。
		
	\end{enumerate}
\end{tcolorbox}

\subsection{抽象的流程表示}
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/8}
	\caption{LL1流程}
	\label{fig:8}
\end{figure}


\begin{algorithm}[H]
	\renewcommand{\thealgocf}{}
	\caption{\texttt{LL(1)分析流程}($G,W$)}
	\KwIn{文法集合$G$ 待匹配目标字符串$W$}
	\KwOut{一个状态，接受字符串或者错误}
	先把'\#'和开始符号压入栈中，从目标字符串左侧中读入一个字符。初始化栈结构 $\mathbf{Stack}$，初始化分析表$\mathbf{T}$。
	\\
	\For {$w \in W\quad and\quad w !='\#'$ }
	{            
		\uIf{$Stack.top()$ is $Non-Terminator$}{generate=lookup(T)
			\\Stack.push(generate.reverse())
			\\Stack.pop()
		}
		\uElseIf{$Stack.top() == w$}{
			Stack.pop()
		}
		\Else{\Return ${"Error"}$}
	}
	\uIf{$Stack.pop() != '\#'$}{\Return ${"Error"}$}
	\Return ${"Accept"}$
	
\end{algorithm}
开始
如果栈顶是非终结符，根据当前元素查找分析表选择产生式，弹出栈顶非终结符，逆序将产生式右部压栈。
如果栈顶是终结符，且与当前元素相同则弹出栈顶元素即可。
否则报错。
循环这个过程直到栈顶和当前元素都是'\#'时，认为可以接受，否则报错。

\section{LL(1)文法及其判定}
前面我们说过LL(1)分析依赖于特定的文法特征，大家可以回忆一下前面所提到的三个基本要点的第三点。同时我们还没有给出一个很规范的流程，怎么得到分析表，这依赖于我们将提出的三个概念。为了更清晰的表达这个概念，我们借助一个具体的文法展开\\
\begin{tcolorbox}[colback=red!5!white,colframe=yellow!75!black,title=文法定义]
	$G(Z)=(V_N, V_T, Z, P)$\\ \\
	$A\rightarrow\alpha$ $\in$ P,这里的$\alpha$是一个串，可以是终结符也可以是非终结符组成。
\end{tcolorbox}
\subsection{首符号集合、后继符集合与选择符集合}

\subsubsection{首符号集合}

\begin{tcolorbox}[colback=yellow!15!white,colframe=yellow!75!black]
	$first(\alpha)=\{t |\alpha \stackrel{*}{\Rightarrow}t...,t\in V_t\}$
\end{tcolorbox}


定义在α上，这里α是一个串，是一个产生式的右部。First集的定义就是，所有α能推导出来的串，这些串的串首的终结符所构成的集合称之为α的first集，也叫首符号集合。通俗一点讲就是，把α能推导出来的第一个终结符的集合，称之为α的首符号集合。
\subsubsection{后继符集合}
\begin{tcolorbox}[colback=yellow!15!white,colframe=yellow!75!black]
	$follow(A)=\{t |Z \stackrel{*}{\Rightarrow}...At...,t\in V_t\}$
\end{tcolorbox}

注意，follow集和first集定义的范围不一样，first集是在一个串，也就是产生式右部上定义的，follow集是在左部，也就是非终结符上定义的。A的follow集表示的是A这个非终结符，在推导的过程中，后面能跟哪些终结符。
\subsubsection{选择符集合}
\begin{tcolorbox}[colback=purple!25!white,colframe=red!75!black]
	
	$$ select(A\rightarrow\alpha)=\left\{
	\begin{aligned}
		&first(\alpha) ,\alpha \stackrel{*}{\nRightarrow}\varepsilon  \\
		&first(\alpha) \cup follow(A) ,\alpha \stackrel{*}{\Rightarrow}\varepsilon
	\end{aligned}
	\right.
	$$
	
\end{tcolorbox}

要形成分析表，只需要观察选择集。选择集定义的范围是在产生式上，比前面first集合在产生式右部、follow集在产生式左部的范围更大一些。当整个文法面临一个非终结符和待生成的终结符，我们应该选择哪一条产生式进行推导。

一个右侧不能推出空的表达式，他的选择集就是他的first集合，这个理由非常明显，既然右侧不能推出空，最后一定会形成一个只有非终结符的串，那这个非空串的串首字符显然就是这个非终结符在碰到它时应选择什么产生式的凭证。

一个右侧能推出空的产生式，他的选择集多了一个产生式左部的follow集合，这也很好理解，因为当非终结符为空的时候，他不会影响那一个紧挨着他的终结符的推导过程，这也是我们前面所说的去牛奶店买牛奶而不是去咖啡店买牛奶（当然也许咖啡店也卖牛奶）。\\


注:
\begin{enumerate}
	\item $\alpha \stackrel{*}{\Rightarrow}\varepsilon$($\alpha$可空), $\alpha \stackrel{*}{\nRightarrow}\varepsilon$($\alpha$不可空)；
	\item 若$\alpha$=$\varepsilon$则 first($\alpha$)=\{ \}是空集；
	\item 设\#为输入串的结束符，则\#∈follow(Z);
\end{enumerate}
这三条注解其实是偏定义的东西，很难说明为什么要这么做。就第一条来说，能推出空他自己就可以是空，不能推出空他自己不能是空，说这么多就是 \textbf{禁止无中生有}，科学也得遵循哲学指导不是。

第二条定义也非常自然，空了啥玩意都推不出来了，那还有啥终结符呢。这个式子就是告诉我们\textbf{一分耕耘，一分收获}，你今天不播种，那肯定没有收成。理解成物质守恒也行，咋好记你就咋记。

唯独需要小心的是第三条，他很容易被忘记，你可以认为每个文法都隐含着这样一条产生式Z$\Rightarrow$Z\#。Z是开始符号，\#是结束符号，用咱中国人的话说那就是\textbf{有始有终}，建议同学们在科学学习中贯穿哲学文化思想。

\subsubsection{一个分析表的构建实例}
经过这么多的定义，得拿起武器开始干活了。大家也学过编程，这个像分段函数一样的选择集定义，在编程上是不是就是个if-else的分支结构。所以我们拿到一个产生式的时候，得先去做个判断，判断啥呢，就是产生式的右侧能不能为空，我们不需要很严谨的把整个产生式都推导到全是终结符，一旦出现一个终结符，就说明右侧不为空了，因为终结符不能继续推导嘛，这个就是\textbf{赚来的钱，交的朋友都可能会离开你，他们是非终结符;学到的知识是终结符，它永远空不了}。



我们从这个文法中说明怎么形成分析表
\\


\begin{tcolorbox}[colback=red!5!white,colframe=yellow!75!black,title=G(Z):]
	
	Z $\rightarrow$ dAZ ①\quad $|$\quad bA   ②   \\
	\quad	A$\rightarrow$aA  ③\quad $|$\quad $\displaystyle\varepsilon$   ④
	
	
\end{tcolorbox}

\ding{172}显然不为空，因为出现了非终结符d；②显然不为空，因为出现了非终结符b；\ding{174}同理不为空；\ding{175}为空。

不为空的\ding{172}\ding{173}\ding{174}，select集合就是first集，分别是d、b、a。

能为空的④，select集合是first集与follow集的并集，但是因为他不是能为空，而是本身是空，根据上面的“物质守恒”原则，他的first集也是空，他的follow集合就是d和b以及\textbf{\#}，这个地方可能有点难，我给你们推荐个经验，先从别的产生式里面找到这个非终结符，如果非终结符后头跟的是终结符，直接塞进follow集，如果跟的是非终结符，把这个后头的非终结符的first集塞进follow集合即可。所以A这个非终结符，出现在了\ding{172}②中。在\ding{172}中，其后跟的是非终结符，把Z的first集合也就是\{d,b\}加入A的follow集合，其次是'\#'，这个根据我们前面提到的“有始有终”原则，所有的开始符号后面都隐含跟随着一个'\#'号，所以②中可以认为是 Z $\rightarrow$ Z\# $\rightarrow$ bA\#，于是A的follow集合就还有\#号。

到这个地方，select集其实就是分析表的等价表示，如果你还没想明白怎么从select集构建分析表，你需要下去花点功夫，当然也许睡一觉起来就想明白了。这个分析表的结果在上面LL1的分析例子中给出来了。


\subsection{LL(1)文法及其判定}
\begin{tcolorbox}[colback=red!5!white,colframe=yellow!75!black,title=LL(1)文法的定义]
	
	LL(1)文法是指文法中，具有相同左部的产生式，其select集合没有交集
	
	
\end{tcolorbox}
这个文法是递归子程序法和LL(1)分析法的使用前提。因为一旦相同左部的产生式的select集有交集，我们就不知道在面对一个元素的时候需要选择哪一条产生式，也就是出现了歧义。

我们举一个新的例子，\\
\begin{tcolorbox}[colback=red!5!white,colframe=yellow!75!black,title=G(Z):]
	
	Z $\rightarrow$ Zb \ding{172} \quad $|$ \quad a  \ding{173} 
	
	
\end{tcolorbox}

$$ 
\because\\
\left .
\begin{aligned}
	select(\textcircled{1})={a} \\
	select(\textcircled{2})={a}
\end{aligned}
\right \}\quad Selection\ set\ intersection
$$
这两个产生式的选择集合相交了，就不属于LL(1)文法了。这里也能看到，在递归子程序里，不能有左递归，一旦有左递归，选择集合一定会相交。具有左递归的文法，一定不是LL(1)文法！那有左递归，该怎么办呢？我们可以尝试把左递归改写成右递归形式。

再扩展一下，左递归有两种，一种是直接左递归，一种是间接左递归，上面的例子是直接左递归，这两种左递归都需要消除。一个通用的算法，如下

\begin{algorithm}
	以某种顺序排列非终结符A1，A2，……，An；\\
	\For{int i = 1; i<=n; i++}{\For{int j = 1; j<=i-1; j++}{将每个形如 Ai → Ajγ 的产生式替换为产生式组 Ａi → ξ1γ｜ξ2γ｜……｜ξkγ ，
			其中，Aj→a1｜a2｜……｜ak是所有的当前Aj产生式}}
	
	消除关于Ai产生式中的直接左递归性
	\}
\end{algorithm}
转换为右递归文法后，select集不相交了\\
\begin{tcolorbox}[colback=red!5!white,colframe=yellow!75!black,title=G'(Z):]
	\centering
	Z$\rightarrow$aA ①\\           A$\rightarrow$bA ②$|$ $\varepsilon$ ③
	
	
\end{tcolorbox}
$$ 
\left .
\begin{aligned}
	select(\textcircled{2})={b} \\
	select(\textcircled{3})={\#}
\end{aligned}
\right \}
$$
$\therefore$ G'(Z)是LL(1)文法，可以使用LL(1)分析。

\section{LL(1)分析器设计(实现)}
分析器由两部分构成，第一部分是分析资源，在LL(1)分析里面就是分析表，第二部分是程序，程序通过读分析表来完成分析过程。
简单的说，就是构建分析表，和利用分析表解析待识别串。
\begin{tcolorbox}[colback=red!15!white,colframe=yellow!75!black]
	\centering
	LL(1)分析表 + LL(1)控制程序
	
	
\end{tcolorbox}
%\clearpage % 换页，\newpage也可以，推荐\clearpage
\subsection{LL(1)分析表的构造}
LL(1)分析表是存储文法选择集合的知识表。表列是终结符，行是非终结符，每个元素是产生式序号。展示一下C++版本的一些粗糙思路供同学们参考。
\begin{lstlisting}[language=C++]
	struct Element{
		int number;	//产生式序号
	}
	//这两个Map需要一段初始化程序，根据你选择的输入方式决定，本质上就是一段从字符串里分离 $\rightarrow$ 左右部分的处理。选择使用map是因为需要一个从char到int的映射，才方便从表里存取表项，很自然的，我们还需要维护两个int类型的index变量，来为每一个独立的char进行一个index++的初始化。这段地方留给同学们自己想想。
	Map<char,int> terminator;
	Map<char,int> Nterminator;
	Element L[terminator.size()][Nterminator.size()];
	//数据结构定义到这里了仍然存在一些小问题，那就是我们该怎么记录产生式，不然我们拿到了序号也没有意义，当然我们可以不存序号，将element类里改成string类型，直接存下产生式的右部，还有很多选择，我就不赘述了，这个地方同学们后期做编译原理课设会有很多机会去实现的。
\end{lstlisting}
这个地方的代码是我根据PPT的意思写的，不太符合工程实现的感觉。你也可以按你喜欢，觉得更工程的方法来完成这个步骤。
如果你已经把数据结构的定义和初始化想好了，那我们可以开始下一个问题，也就是分析表的初始化。这个需要我们去求first和follow集合，还是挺有挑战性的。我是这么想的，如果对编程不熟悉的同学，可以考虑手动输入每个产生式的first和follow集合；如果编程能力比较强的同学，可以尝试自动从产生式里解析出来first和follow集合，因为后期课设的产生式非常多非常丰富，如果纯靠脑袋去想会很累，当然最重要的是很不酷。

我给出一点我的想法，希望是启发，不是约束。我尽可能避开具体的代码，只给出注释。
\begin{lstlisting}[language=C++]
	map<char,set<char> firstSet;
	void genFirstSet(){
		//先初始化终结符的firstset，当然是自身。
		for(){
			//遍历终结符集合，逐个插入对应的firstSet中
		}
		
		//这里是难度重头戏，需要遍历产生式，为非终结符生成firstSet，我建议流程是这样的。
		// 这里应该有一个循环
		while(){
			// 取出产生式的左部，去firstSet里面拿到其对应的firstSet，可能是空，也可能是不完整的firstSet，也可能是完整的。
			//判断这个产生式的右部是不是终结符或者是空，且是否存在这个左部的firstSet中，不在就加入
			//否则如果是非终结符，判断右部第一个字符能不能是空，如果能，就把他的firstSet复制过来，继续往后看，这里应有一个循环。
			//如果右侧第一个非终结符不空，那直接复制firstSet就好
			//这里还有个小困难，就是如何结束这个循环，我建议是当没有改变时逃出，通过维护一个bool变量，在有改变的分支里不断变换他的值，在循环一开始改动他的值。
		}
	}
	
\end{lstlisting}

first集合的自动生成大概如上所示，一个定义的不错的结构，会让你的思路事半功倍，如果做完first集合生成，相信follow集合也不会难倒你.加油.


接着是生成select集合，这个地方根据上面的定义做就好。在做完这一切，得到分析表之后，你可以看一下
\begin{figure}[H]
	\centering
	\includegraphics[width=1\linewidth]{pic/9}
	\caption{流程图}
	\label{fig:9}
\end{figure}

我们回头再梳理一遍要做的事情
\begin{enumerate}
	\item 消除左递归
	\item 生成firstSet
	\item 生成followSet
	\item 生成selectSet
	\item 生成分析表
	\item 借助控制程序进行分析
\end{enumerate}
